COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a06.tex[154,phy] \today\hfill}
\parskip 6pt

\def\starp{\buildrel\ast\over\Rightarrow}
\def\narp{\buildrel n\over\Rightarrow}
\def\nnap{\buildrel n-1\over\Rightarrow}


\bigskip
\line{CS 154\hfill Spring 1983}
\line{Prof. R. W. Floyd\hfill}

\bigskip

A function $f$ from sets to sets is {\sl monotone} if $X\subseteq Y$ implies
$f(X)\subseteq f(Y)$.  A monotone function is {\sl continuous\/} if, letting
$X↓1\subseteq X↓2\subseteq X↓3\subseteq\ldots\,$, and $X↓∞=∪ X↓i,\, f(X↓∞)=∪
f(X↓i)$.  Equivalently (for countable sets),
it is continuous if, for each $z\in F(X)$, there is a
finite subset $X'\subseteq X$, for which $z\in f(X')$.  Another
definition: $f$ is continuous if $f(X)=∪ f(Y)$ for the sets $Y$ which are
finite subsets of $X$.  Analogous definitions apply to functions of several 
variables.

An example of a  non-monotone set function is $X-Y$; an example of a
non-continuous set function is
$$\eqalign{f(X)&=X\ {\rm if\ }X\ {\rm is\ finite}\cr
f(X)&=X∪\{\epsilon\}\ {\rm if\ }X\ {\rm is\ infinite}.\cr}$$
(Try it on $X↓i=\{a,a↑2,\ldots,a↑i\}$.)

\medskip
\noindent
{\sl Exercise\/}: show the three definitions equivalent for countable
sets, such as languages.

\medskip
\noindent
Suppose $f$ and $g\in S\times S→S$ are monotone and continuous.  We shall show that 
the simultaneous equations:
$$\eqalign{X&=f(X,Y)\cr
Y&=g(X,Y)\cr}$$
have a solution; indeed, there is a unique minimum solution.  Define $X↓0=Y↓0=
\emptyset$; $X↓{i+1}=f(X↓i,Y↓i)$, $Y↓{i+1}=g(X↓i,Y↓i)$.  
An easy induction shows $X↓i
\subseteq X↓{i+1}$, $Y↓i\subseteq Y↓{i+1}$.  Let $X↓∞=∪ X↓i$, $Y↓∞=∪ Y↓i$.  
We show $X↓∞=f(X↓∞,Y↓∞)$, 
$Y↓∞=g(X↓∞,Y↓∞)$.

\medskip
\noindent
{\sl Proof\/}:

\smallskip
\disleft 25pt:(1):$X↓∞\subseteq f(X↓∞,Y↓∞)$. If $z\in X↓∞$, $z\in X↓i=
f(X↓{i-1},Y↓{i-1})$ for some $i≥1$;
by monotonicity, since $X↓{i-1}\subseteq X↓∞$, etc., $z\in f(X↓∞,Y↓∞)$. 

\smallskip
\disleft 25pt:(2):$f(X↓∞,Y↓∞)\subseteq X↓∞$.  
If $z\in f(X↓∞, Y↓∞)$, $z\in f(X',Y')$
for finite subsets $X'\subseteq X↓∞$, $Y'\subseteq Y↓∞$.
Then there is an $i$ such that $X'\subseteq X↓i$, $Y'\subseteq Y↓i$;
$z\in f(X↓i,Y↓i)=X↓{i+1}\subseteq X↓∞$.

\medskip\noindent
This gives us the

\medskip

\noindent
{\sl Theorem\/}: a monotone, continuous set function has a fixed point.

\medskip
To show it has a least fixed point, show by induction that
$X↓i$, $Y↓i$  (defined above) are subsets of any
sets that satisfy the equations.

\medskip\noindent
{\sl Exercise\/}: show that monotonicity and continuity are closed 
under composition.

\medskip

The regular operations (union, concatenation, and Kleene closure) are all
monotone and continuous, so if we define
$$\eqalign{X&=r↓1(X,Y)\cr
Y&=r↓2(X,Y)\cr}$$
where $r↓1$ and $r↓2$ are regular expressions containing the variables
$X$ and $Y$, there is a unique minimum fixed point, the
languages $X$ and $Y$ defined by these operations.  Omitting the Kleene closure,
we can still define the same languages: 
rather than using~$U↑{\ast}$, we define
$V=\epsilon +VU$; the reader should confirm that 
$V↓∞=\epsilon +U+UU+UUU+\cdots =U↑{\ast}$. 
The languages so definable as minimum fixed points using the regular operations
are the {\sl context-free} languages.  To show that this definition is equivalent
to the usual one:

If $X\starp z$, then $X\narp z$ (derivable by a tree of depth $≤n$)
for some $n$.
By induction on $n$, if $n>0$, then
$X→A↓1A↓2\cdots A↓k$, $A↓i\nnap z↓i$, 
$z=z↓1z↓2\cdots z↓k$;
$z↓i\in (A↓i)↓∞$, so
$X↓∞=(A↓1)↓∞(A↓2)↓∞$, etc., and the strings derivable from the variables form a
fixed point.  Furthermore they can be shown to be a subset of any fixed point, so 
they form the minimum fixed point.
[RWF: clean up above argument.]

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft November 13, 1984

\bye